/*
 * @lc app=leetcode.cn id=139 lang=typescript
 *
 * [139] 单词拆分
 */

// @lc code=start

//  思路：动态规划
//  dp[i]表示s(0,i)能否被拆成单词表内的单词
//  dp[i] = dp[j] && s(j,n-1) in wordDict  i: 0~len, j:0~i
//  每次i的循环，通过j进行分段，前段可以利用dp内之前计算的值，后段通过哈希查询是否在字典中，如果前段、后段均满足条件，则当前选取的区间满足条件

function wordBreak(s: string, wordDict: string[]): boolean {
    const len = s.length
    // 哈希存储，O(1)判断是否存在
    const dict = new Set(wordDict)
    const dp = new Array(len + 1).fill(false)
    // 赋初始值
    dp[0] = true

    for (let i = 1; i <= len; i++) {
        for (let j = 0; j < i; j++) {
            // 剪枝
            if (dp[i] == true) break;
            if (dp[j] == false) continue;

            const sub = s.substring(j, i)
            if (dp[j] && dict.has(sub)) {
                dp[i] = true
                break
            }
        }
    }
    return dp[len]
};
// @lc code=end


console.log(wordBreak("applepenapple", ["apple", "pen"]));

